package leetcode.nod;

public class Lc427_2 {

    int[][] preSum;

    //二维数组前缀和优化版本，用前缀和判断一个区域是否所有的格子值都相同，即是否为叶子节点
    public Node construct(int[][] grid) {

        preSum = new int[grid.length + 1][grid.length + 1];
        for (int i = 1; i <= grid.length; i++) { //grid[i][j]表示grid[0][o]~grid[i-1][j-1]这个矩形区域内的值的和
            for (int j = 1; j <= grid.length; j++) {
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + grid[i- 1][j - 1];
            }
        }
        return getNodeRoot(grid, 0, grid.length, 0, grid.length);

    }

    public Node getNodeRoot(int[][] grid, int xs, int xe, int ys, int ye) {
        int sum = getSum(xs, xe, ys, ye);
        if (sum == 0) {
            return new Node(false,true);
        } else if (sum == (xe - xs) * (ye - ys)) {
            return new Node(true,true);
        }
        Node topLeft = getNodeRoot(grid, xs, (xs + xe) / 2, ys, (ys + ye) / 2);
        Node topRight = getNodeRoot(grid, xs, (xs + xe) / 2, (ys + ye) / 2 , ye);
        Node bottomLeft = getNodeRoot(grid, (xs + xe) / 2 , xe, ys, (ys + ye) / 2);
        Node bottomRight = getNodeRoot(grid, (xs + xe) / 2, xe, (ys + ye) / 2, ye );
        Node root = new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
        return root;

    }
    int getSum(int xs, int xe, int ys, int ye) {
        return preSum[xe][ye] - preSum[xe][ys] - preSum[xs][ye] + preSum[xs][ys];
    }


}
